beyondbinaryfandomcom-20200215-history
Kolmogorov Complexity
|Wikipedia:/en/Kolmogorov Complexity> Introduction * *Kolmogorov Complexity* is to *Information Theory* *_________________as___________________ * *Carnot Efficiency* is to *Thermodynamics*, in my estimation. It sets the lower limit for the size of a program to generate some output of a fixed complexity. One might think that a program can be arbitrarily optimised if it only has to generate a single output, however no output can be generated from nothing. Even a program that outputs nothing but "Hello world" takes a few lines of code. You can optimise your language for the task, even write a language in which "1" means "Hello World" and "0" calls a function to print the next input. A program in such a language simply needs to be written as "01" and it will produce the desired output, but even this tiny program has a size of 2 bits. The minimum complexity for any program is 0 bits, but this is a null program. A null program in any language is incapable of doing anything. You could write a language in which null programs print "Hello world" by default, but then how many null programs will in run per second? How much nothing is there in one second? You can't divide by 0, so any logical language needs its programs to have more than 0 bits. This allows us to set a minimum complexity. If your desired output is 0 bits - then the optimal program is 0 bits. (0/0 divides nothing by 0, hence it's ok) If your desired output is > 0 bits - then the optimal program is also more than 0 bits in size (N/0 is not allowed for N!=0) The optimal size is known as the "Kolmogorov Complexity" of that output. Invariance Theorem - the choice of encoding language is unimportant (up to some additive constant) This puzzles me... surely if you want to print "Hello world" then it could take a program of "print("Hello world")" = 20 characters = 160 bits (ASCII) or if you made a new language that says 0="print(" and 1=""Hello world")" then you could reduce this to just 2 bits in a program saying "01"? So then I've reduced the complexity from 160 to 2, which is an additive constant of -158. Is this not important? Universal Turing Machines I'm pretty sure the reason that this argument fails is because you have essentially just hidden part of the complexity in your language compiler. However, a computer that doesn't have that language compiler pre-installed to memory (i.e. a "universal computer", rather than a specialised one for writing "Hello world" when it gets "01" as an input) would not be able to produce that output from such a short program. I'm not sure where you draw the line, but I guess that's a long-solved issue in computer science in terms of translating programming languages into universally computable algorithms. I will have to learn about that facet later. https://en.wikipedia.org/wiki/Kolmogorov_complexity#Uncomputability_of_Kolmogorov_complexity https://en.wikipedia.org/wiki/Code_golf Quantum Kolmogorov Complexity |C.Rogers,V.Vedral:/2005/The Second Quantized Quantum Turing Machine and Kolmogorov Complexity> :"The Kolmogorov complexity of a physical state is the minimal physical resources required to reproduce that state. We define a second quantized quantum Turing machine and use it to define second quantized Kolmogorov complexity. There are two advantages to our approach - our measure of second quantized Kolmogorov complexity is closer to physical reality and unlike other quantum Kolmogorov complexities it is continuous. We give examples where second quantized and quantum Kolmogorov complexity differ." :"Since we want to know what is physically the shortest input which produces a given output, we need allow the computation with superpositions of different length programs. :This letter is organized as follows. First we discuss the concept of a Turing machine and review previous work.Then we define the fully quantum Turing machine (we call it second quantized for reasons that will become apparent below). We use this second quantized Turing machine (SQTM) to define the concept of second quantized Kolmogorov complexity (SQKC). This notion is then tested by applying it to various simple examples such as the average length of two programs of different sizes and programs which halt at a superposition of different times. We consider conditional complexity and show that multiple copies of a quantum state can be compressed asymptotically further using SQTM than on a standard quantum Turing machine (QTM) given the number of copiesn." E:Vedral Quantum Ephemeral Economics Forget the idea of a blockchain as a permanent ledger of transactions, all ledgers are imperfect. Accept uncertainty. Fully ephemeral economics does not require 100% verification of inputs and outputs, the nanoeconomy simply needs to maintain equilibrium on the whole. Hence, not only can future transactions have uncertainty (a flaw common to any economy) but an ephemeral economy is able to allow time-symmetry in allowing for uncertainty in past transactions also. Cryptocurrencies likes Bitcoin are incapable of providing a real alternative to Capitalism because they reward centralisation of mining power and currency stake in the same ways that Capitalism does, despite their presumed goals of Decentralisation. In such an economy, the problem of trading becomes much more open: Rather than asking "Who will trade me X of Y-coin for Q of Z-coin?" One simply asks "Can anyone guarantee me X of Y-coin, given a budget of Q of Z-coin?" We implicitly move from a P2P trading system to a cloud-trading network, in which many micro-transactions can add together to produce the desired results. Creation Ex Nihilo |InternationalSkeptics:/BenRayfield/2010/"My theory of everything is: The Kolmogorov Complexity of the universe is 0."> :"If the laws of physics are exactly "The Kolmogorov Complexity of the universe is 0" then the laws of physics would never change but could appear to become any equations. I simply think the laws of physics are more general than most scientists think is possible. I can easily write the same thing without saying the laws of physics change. Instead, the laws of physics are the things that calculate new equations that would be written in physics books. :I'm agreeing with you. I'm proposing that the next step in physics (like from Newton to Einstein) is using thermodynamics in a fractal way instead of completely linear. It appears linear locally but for the whole universe is curved into a fractal." :"It means, as many eastern philosophies speculate, that the universe is balanced in an infinite number of ways, that anything you can write in math exists somewhere, and when viewed together, all sums to zero, so technically the universe would not exist on average, if its kolmogorov complexity is 0. Kolmogorov complexity is the technical phrase for how much total information is in something. Example: "All the integers" contains less information than "all the integers except 37 and 50" because its shorter to write. It means the universe would fit in a 0 byte zip file, if it could be represented in a computer, which it can't except for an empty file." Links |StimulatedAnnealing:/WordPress/Kolmogorov Complexity, Autism, and Music>] :"I think algorithmic information theory is one of the most interesting subfields of information theory and computer science. Much of my interest comes from the fact that algorithmic information theory is an interdisciplinary subject: Gregory Chaitin described it as “the result of putting Shannon’s information theory and Turing’s computability theory into a cocktail shaker and shaking vigorously”." :"Kolmogorov complexity defines the algorithmic complexity of an object as the length of the shortest binary computer program needed to specify that object. For example, the Mandelbrot set looks quite complicated, but it has near-zero Kolmogorov complexity because the length of a program needed to compute the Mandelbrot set is so small. The “objects” considered in complexity theory are usually bitstrings (unsurprisingly, given how strongly the field has been influenced by, and also influenced, computer science)." |Wikipedia:/en/Incompressibility method> "The incompressibity method depends on an objective, fixed notion of incompressibility. Such a notion was provided by the Kolmogorov complexity theory, named for Andrey Kolmogorov.1 One of the first uses of the incompressibility method with Kolmogorov complexity its theory of computation was to2 prove that the running time of a one-tape Turing machine is quadratic for accepting a palindromic language and sorting algorithms require at least n log ⁡(n) time to sort n items." ---- numpage=2094[=15[=6 (last 5 was ???) 2094=1047*2=349*3*2 Factors=1 , , , 2 , , 3 , , , 6 , , , , , , , , , , , , , , , , , 349 , , , 698 , , 1047 , , , 2094 Category:Information Theory Category:Quantum Information Theory Category:Entropy Category:Information Age Category:Statistics Category:Communication Category:Programming Category:Code Category:Mathematics Category:Fractals